package k3;

import java.io.IOException;
import java.util.ArrayList;


public class Main {

	/**
	 * @param args
	 * @throws IOException 
	 */
	public static void main(String[] args) throws IOException {
		int i;
		String fileName="100";
		String strLine;
		int index;
		int totalWeight;
		BagState best;
		Knapsack knapsack = new Knapsack();
		Item item;
		ArrayList<String> lines = Utils.readFile(fileName);
		ArrayList<Item> objects = new ArrayList<Item>();
		totalWeight=Integer.parseInt(lines.get(0));
		for(i=1;i<lines.size();i++){
			strLine=lines.get(i);
			index=strLine.indexOf(' ');
			item=new Item(Integer.parseInt(strLine.substring(0, index)), Integer.parseInt(strLine.substring(index+1)));
			objects.add(item);
		}
		long startTime=System.currentTimeMillis();
		best=knapsack.depth_first_branch_and_bound(objects, totalWeight);
		System.out.println("execution time in ms: "+(System.currentTimeMillis()-startTime));
		System.out.println(best.value+" "+best.weight);
		objects=knapsack.findObjectsAdded(best);
		lines.clear();
		lines.add(best.value+" "+best.weight);
		for(i=0;i<objects.size();i++){
			System.out.println(objects.get(i).value+" "+objects.get(i).weight);
			lines.add(objects.get(i).value+" "+objects.get(i).weight);
		}
		Utils.writeFile(lines, fileName);
	}

}
